Pairwise independent hash families #
A family of functions h i : X → Y, indexed by a seed i drawn uniformly from a finite type ι,
is pairwise independent (Cslib.Probability.IsPairwiseIndependentHash) if each value h i x is
uniformly distributed on Y and the values at any two distinct points are independent
Arora and Barak, Definition 8.14. Wegman and Carter call such families strongly
universal₂ [WC81], after the universal families of [CW79]. Probabilities
over the seed are densities Finset.dens of sets of seeds, and averages are uniform expectations
𝔼 i.
Fix a finite set S ⊆ X and a target y : Y. The size N i = #{x ∈ S | h i x = y} of the
cell of y has mean μ = #S / |Y| and second factorial moment
𝔼 N (N - 1) = #S (#S - 1) / |Y|², so its variance is μ (1 - 1 / |Y|) ≤ μ, and Chebyshev's
inequality bounds its deviations. For the probability that S hits y:
- it is at most
μ(IsPairwiseIndependentHash.dens_filter_mem_image_le), so at most1 / kwhenk #S ≤ |Y|; Smissesywith probability at most1 / μ(IsPairwiseIndependentHash.dens_filter_notMem_image_le), soShitsywith probability at least1 - 1 / kwhen#S ≥ k |Y|;- it is at least
μ - #S (#S - 1) / (2 |Y|²)by inclusion–exclusion, hence at least3 μ / 4when2 #S ≤ |Y|: the analysis of the set lower bound protocol of Goldwasser and Sipser [GS86] in Arora and Barak, Section 8.2.
The same argument shows that exactly one element of S hits y with probability at least
μ - #S (#S - 1) / |Y|², hence at least 3 / 16 when |Y| ≤ 4 #S ≤ 2 |Y|: the lemma of Valiant
and Vazirani [VV86] in Arora and Barak, Section 17.4, where the bound
is 1 / 8.
Main definitions #
Cslib.Probability.IsPairwiseIndependentHash: pairwise independent hash families.
Main results #
Cslib.Probability.IsPairwiseIndependentHash.expect_card_filter_apply_eq,Cslib.Probability.IsPairwiseIndependentHash.expect_card_filter_mul_card_filter_sub_one: the first two factorial moments of the size of a cell.Cslib.Probability.IsPairwiseIndependentHash.expect_card_filter_sub_sq: its variance.Cslib.Probability.IsPairwiseIndependentHash.dens_filter_le_abs_sub_le: Chebyshev's inequality.Cslib.Probability.IsPairwiseIndependentHash.dens_filter_mem_image_le,Cslib.Probability.IsPairwiseIndependentHash.dens_filter_notMem_image_le: the probability thatShits a target is at mostμ, and that it misses it at most1 / μ.Cslib.Probability.IsPairwiseIndependentHash.three_quarters_mul_le_dens_filter_mem_image: the set lower bound protocol.Cslib.Probability.IsPairwiseIndependentHash.four_mul_card_filter_notMem_image_le,Cslib.Probability.IsPairwiseIndependentHash.four_mul_card_filter_mem_image_le: in counts, a target is missed by at most a quarter of the seeds when#S ≥ 4 |Y|, and hit by at most a quarter when4 #S ≤ |Y|.Cslib.Probability.IsPairwiseIndependentHash.comp_seedEquiv: relabelling seeds.Cslib.Probability.IsPairwiseIndependentHash.three_sixteenths_le_dens_filter_card_filter_eq_one: the Valiant–Vazirani lemma.
References #
- S. Arora, B. Barak, Computational Complexity: A Modern Approach
- J. L. Carter, M. N. Wegman, Universal classes of hash functions
- M. N. Wegman, J. L. Carter, New hash functions and their use in authentication and set equality
- S. Goldwasser, M. Sipser, Private coins versus public coins in interactive proof systems
- L. G. Valiant, V. V. Vazirani, NP is as easy as detecting unique solutions
A family of functions h i : X → Y, indexed by a seed i : ι drawn uniformly at random, is
pairwise independent if every value h i x is uniformly distributed on Y, and the values
h i x₁ and h i x₂ at distinct points are independent: a 1 / |Y| fraction of the seeds sends
x to y, and a 1 / |Y|² fraction sends x₁ ≠ x₂ to y₁ and y₂. The first condition
follows from the second unless X has exactly one element.
Every value is uniformly distributed.
- dens_filter_apply_eq_and_apply_eq {x₁ x₂ : X} (hx : x₁ ≠ x₂) (y₁ y₂ : Y) : {i : ι | h i x₁ = y₁ ∧ h i x₂ = y₂}.dens = (↑(Fintype.card Y) ^ 2)⁻¹
The values at two distinct points are independent.
Instances For
A pairwise independent family with a point x : X and a value y : Y has a seed.
Restricting a pairwise independent family along an injective map keeps it pairwise independent.
Relabelling seeds: precomposing the seeds of a pairwise independent family with an equivalence keeps it pairwise independent.
The mean cell size: #{x ∈ S | h i x = y} has expectation #S / |Y|.
The second factorial moment of the cell size: N (N - 1), the number of ordered pairs of
distinct elements of the cell N = #{x ∈ S | h i x = y}, has expectation #S (#S - 1) / |Y|².
The variance of the cell size: #{x ∈ S | h i x = y} has variance
#S / |Y| * (1 - 1 / |Y|).
The variance of the cell size is at most its mean #S / |Y|.
Chebyshev's inequality for the cell size: #{x ∈ S | h i x = y} is at distance at least
ε > 0 from its mean μ = #S / |Y| with probability at most μ / ε².
First moment bound: S hits y with probability at most the mean cell size
#S / |Y|.
Second moment bound: a nonempty S misses y with probability at most the inverse
|Y| / #S of the mean cell size.
A nonempty S hits y with probability at least 1 - |Y| / #S.
Large sets are hit: if #S ≥ 4 |Y|, at most a quarter of the seeds miss a target, in
counts.
Small sets are missed: if 4 #S ≤ |Y|, at most a quarter of the seeds hit a target, in
counts.
Inclusion–exclusion for hitting a target: S hits y with probability at least
#S / |Y| - #S (#S - 1) / (2 |Y|²).
The set lower bound protocol of Goldwasser and Sipser: if 2 #S ≤ |Y|, then S hits y
with probability at least three quarters of the mean cell size #S / |Y|
Arora and Barak, Section 8.2.
Inclusion–exclusion for a unique preimage: exactly one element of S hits y with
probability at least #S / |Y| - #S (#S - 1) / |Y|².
The Valiant–Vazirani lemma: if |Y| ≤ 4 #S ≤ 2 |Y|, then exactly one element of S hits
y with probability at least 3 / 16 Arora and Barak, Section 17.4.