Robust Fuzzy Extractors and Authenticated Key Agreement From Close Secrets

Consider two parties holding samples from correlated distributionsWandW^, respectively, where these samples are within distancetof each other in some metric space. The parties wish to agree on a close-to-uniformly distributed secret keyRby 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 secretSKExtthat they can use to generate a sequence of session keysⱼ multiple pairs\(Wⱼ, W^ⱼ)\. 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.The best prior solution for the keyless case with no errors (i.e.,$t=0$) requires the min-entropy ofWto exceed$2n/3$, wherenis the bit length ofW. Our solution applies whenever the min-entropy ofWexceeds the minimal threshold$n/2$, and yields a longer key.