Fuzzy extractor

A fuzzy extractor derives from a noisy secret , such as a biometric reading, a nearly uniform key and public helper data , such that any reading close to recovers from , while stays close to uniform given whenever has enough min-entropy — DRS04, DORS08.

Syntax

Let be a metric space, such as with Hamming distance or the subsets of a universe with the size of the symmetric difference. A fuzzy extractor for with key length and error tolerance is a pair of algorithms :

  • , a randomized algorithm that takes and outputs a key and a helper string ,
  • , a deterministic algorithm that takes and a helper string and outputs a key.

Properties

Correctness

For all with , if then — DORS08.

Security

A fuzzy extractor is an -fuzzy extractor if for every distribution on with min-entropy and every distinguisher , of unbounded running time,

\begin{algorithm}
\algname{Game}
\caption{$\Game^{\mathrm{fe}}_{(\Gen, \mathsf{Rep}),W,\calA}$}
\begin{algorithmic}
\State $w \gets W$; $(R_0, P) \gets \Gen(w)$; $R_1 \getsr \bits^\ell$; $b \getsr \bits$
\State $b' \gets \calA(R_b, P)$
\Return $[b' = b]$
\end{algorithmic}
\end{algorithm}

equivalently, the statistical distance between and is at most — DORS08.

Variations

Secure sketches

A secure sketch is a pair with randomized and deterministic such that whenever ; it is an -secure sketch if for every with the average min-entropy satisfies . The difference is its entropy loss — DORS08.

A secure sketch and a strong extractor for average min-entropy give a fuzzy extractor: outputs for a uniform seed and , and recovers with and recomputes . Instantiated with universal hashing, an -secure sketch yields an -fuzzy extractor with , by the leftover hash lemma for average min-entropy (Secure sketch ⇒ Fuzzy extractor) — DORS08.

Robust and reusable fuzzy extractors

A robust fuzzy extractor lets detect, with high probability, a helper string modified by an adversary, which makes it usable for authentication over channels that the adversary controls — BDKOS05. A reusable fuzzy extractor stays secure when is run on several correlated readings of the same source; Boy04 defines reusability and shows that it does not hold for every fuzzy extractor.

Computational fuzzy extractors

A computational fuzzy extractor for a family of sources on requires to be computationally indistinguishable from for every source in the family — FMR13. Secure sketches defined with conditional HILL pseudoentropy imply error-correcting codes, so they are subject to the coding-theoretic bounds of information-theoretic sketches — FMR13. Analyzed directly, a computational fuzzy extractor from LWE outputs a key as long as the source’s entropy, which is impossible information-theoretically, for uniform and symbol-fixing sources — FMR13.

TODO: the definition of FMR13, stated from the paper: the source family, key length , error tolerance , correctness error, and the distinguisher size and advantage bound. Also state the regime of its LWE theorem (source class, key length), before this notion is registered as a variant.

Other results

  • Code offset. For a -ary code of length with codewords that corrects errors, for a uniform codeword , with decoding to the nearest codeword and outputting , is a secure sketch for the Hamming metric on with entropy loss at most — DORS08; for it is the offset component of the fuzzy commitment of JW99, which also publishes a hash of . For a linear code the sketch can be the syndrome of , a deterministic function with the same entropy loss — DORS08.
  • Set difference. For subsets of a universe of size , the PinSketch construction from BCH codes has entropy loss at most , independent of the size of the sets — DORS08.

Participates in

Builds on Fuzzy extractor

Produces Fuzzy extractor