Because we make no computational assumptions, the entropy in R can come only from w. Thus such a protocol must minimize the entropy loss during its execution, so that R is as long as possible. The best previous results have entropy loss of $\Theta(\kappa^2)$, where $\kappa$ is the security parameter, thus requiring the password to be very long even for small values of $\kappa$. In this work, we present the first protocol for information-theoretic key agreement that has entropy loss LINEAR in the security parameter. The result is optimal up to constant factors. We achieve our improvement through a somewhat surprising application of error-correcting codes for the edit distance.
The protocol can be extended to provide also ``information reconciliation,'' that is, to work even when the two parties have slightly different versions of w (for example, when biometrics are involved).Category / Keywords: foundations / Privacy Amplification, Information-theoretic Key Agreement Publication Info: This is an expanded and corrected version of a paper published at STOC 2010 Date: received 30 Aug 2012 Contact author: bhavanak at cs bu edu Available formats: Postscript (PS) | Compressed Postscript (PS.GZ) | PDF | BibTeX Citation Version: 20120903:130238 (All versions of this report) Discussion forum: Show discussion | Start new discussion