Consider two parties holding samples from correlated distributions W and W', respectively, where these samples are within distance t of each other in some metric space. These parties wish to agree on a close-to-uniformly distributed secret key R by sending a single message over an insecure channel controlled by an all-powerful adversary who may read and modify anything sent over the channel. We consider both the keyless case, where the parties share no additional secret information, and the keyed case, where the parties share a long-term secret SK_{Ext} that they can use to generate a sequence of session keys {R_{j}} using multiple pairs {(W_{j}, W'_{j})}. The former has applications to, e.g., biometric authentication, while the latter arises in, e.g., the bounded storage model with errors.
We show solutions that improve upon previous work in several respects:
You may want to see the related survey and a prior paper.
A preliminary version of this work appears in Advances in Cryptology -- Crypto 2006, Cynthia Dwork, editor, Lecture Notes in Computer Science 4117, pages 232-250, Springer-Verlag, 2006. It contains an incorrect claim (Corollary 2) about the existence of robust fuzzy extractors for the edit distance.
The version posted here corrects the above error and some other minor errors and adds many clarifications and proofs. It also incorporates results from this follow-up work. It appears in IEEE Transactions on Information Theory 58(9), pp. 6207-6222, 2012.