Fuzzy extractors are a method that allows biometric data to be used as inputs to standard cryptographic techniques, to enhance computer security. "Fuzzy," in this context, refers to the fact that the fixed values required for cryptography will be extracted from values close to but not identical to the original key, without compromising the security required. One application is to encrypt and authenticate users records, using the biometric inputs of the user as a key. Fuzzy extractors are a biometric tool that allows for user authentication, using a biometric template constructed from the user's biometric data as the key, by extracting a uniform and random string R {\displaystyle R} from an input w {\displaystyle w} , with a tolerance for noise. If the input changes to w ′ {\displaystyle w'} but is still close to w {\displaystyle w} , the same string R {\displaystyle R} will be re-constructed. To achieve this, during the initial computation of R {\displaystyle R} the process also outputs a helper string P {\displaystyle P} which will be stored to recover R {\displaystyle R} later and can be made public without compromising the security of R {\displaystyle R} . The security of the process is also ensured when an adversary modifies P {\displaystyle P} . Once the fixed string R {\displaystyle R} has been calculated, it can be used, for example, for key agreement between a user and a server based only on a biometric input.
History One precursor to fuzzy extractors was the so-called "Fuzzy Commitment", as designed by Juels and Wattenberg. Here, the cryptographic key is decommitted using biometric data. Later, Juels and Sudan came up with Fuzzy vault schemes. These are order invariant for the fuzzy commitment scheme and use a Reed–Solomon error correction code. The code word is inserted as the coefficients of a polynomial, and this polynomial is then evaluated with respect to various properties of the biometric data. Both Fuzzy Commitment and Fuzzy Vaults were precursors to Fuzzy Extractors.
Motivation In order for fuzzy extractors to generate strong keys from biometric and other noisy data, cryptography paradigms will be applied to this biometric data. These paradigms: (1) Limit the number of assumptions about the content of the biometric data (this data comes from a variety of sources; so, in order to avoid exploitation by an adversary, it's best to assume the input is unpredictable). (2) Apply usual cryptographic techniques to the input. (Fuzzy extractors convert biometric data into secret, uniformly random, and reliably reproducible random strings.) These techniques can also have other broader applications for other type of noisy inputs such as approximative data from human memory, images used as passwords, and keys from quantum channels. Fuzzy extractors also have applications in the proof of impossibility of the strong notions of privacy with regard to statistical databases.
Basic definitions
Predictability Predictability indicates the probability that an adversary can guess a secret key. Mathematically speaking, the predictability of a random variable A {\displaystyle A} is max a P [ A = a ] {\displaystyle \max _{\mathrm {a} }P[A=a]} . For example, given a pair of random variable A {\displaystyle A} and B {\displaystyle B} , if the adversary knows b {\displaystyle b} of B {\displaystyle B} , then the predictability of A {\displaystyle A} will be max a P [ A = a | B = b ] {\displaystyle \max _{\mathrm {a} }P[A=a|B=b]} . So, an adversary can predict A {\displaystyle A} with E b ← B [ max a P [ A = a | B = b ] ] {\displaystyle E_{b\leftarrow B}[\max _{\mathrm {a} }P[A=a|B=b]]} . We use the average over B {\displaystyle B} as it is not under adversary control, but since knowing b {\displaystyle b} makes the prediction of A {\displaystyle A} adversarial, we take the worst case over A {\displaystyle A} .
Min-entropy Min-entropy indicates the worst-case entropy. Mathematically speaking, it is defined as H ∞ ( A ) = − log ( max a P [ A = a ] ) {\displaystyle H_{\infty }(A)=-\log(\max _{\mathrm {a} }P[A=a])} . A random variable with a min-entropy at least of m {\displaystyle m} is called a m {\displaystyle m} -source.
… excerpt ends here. Continue reading the full article.
