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, last revised 23 Jun 2014 Contact author: bhavana at csa iisc ernet in Available format(s): PDF | BibTeX Citation Version: 20140623:063606 (All versions of this report) Discussion forum: Show discussion | Start new discussion