Leftover hash lemma

A family of functions is 2-universal (universal) if for all distinct , — CW79. A random variable on has min-entropy , and denotes statistical distance.

Let be a 2-universal family of functions and a random variable on with . For independent of and uniform on independent of ,

— ILL89, HILL99. In particular, gives distance at most .

Proof

For a random variable on a finite set with independent copy , write . By Cauchy–Schwarz,

Take on , with identified with its index set, and an independent copy . Then , distinct inputs collide under with probability at most , and so

Hence , and is uniform on — standard.

The proof uses only through , so the bound holds whenever the collision entropy is at least . For a family of functions into a finite set with collision probability at most on distinct inputs, the same argument gives — standard.

2-universal families

Every pairwise-independent family is 2-universal — standard. The linear maps for form a 2-universal family, since for — CW79.

Average min-entropy

For a pair of random variables , the average min-entropy of given is

If takes at most values, then , since — DORS08.

For every 2-universal family of functions and every pair with on and , with independent of and uniform and independent of ,

so gives distance at most — DORS08. Conditioned on , the lemma bounds the distance by ; averaging over and applying Jensen’s inequality to the concave gives the bound.

Participates in

Used via Leftover hash lemma