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
- CRHF ⇒ Statistically hiding COM
- Lossy TDF ⇒ OT
- Lossy trapdoor functions ⇒ IND-CCA PKE
- LWE ⇒ Selectively secure HIBE (bonsai trees)
- LWE with sub-exponential ratio ⇒ Leveled FHE (BGV12)
- LWE with polynomial ratio ⇒ Leveled FHE (BV14)
- LWE ⇒ PKE
- OWF ⇒ PRG
- Secure sketch ⇒ Fuzzy extractor
- Sub-exponential LWE ⇒ CPA-secure PKE
- LWE at sub-exponential and polynomial ratios ⇒ Bootstrappable SHE (BV11)
- Universal HPS ⇒ LR-PKE