Paper 2008/494

Key Agreement from Close Secrets over Unsecured Channels

Bhavana Kanukurthi and Leonid Reyzin


We consider information-theoretic key agreement between two parties sharing somewhat different versions of a secret w that has relatively little entropy. Such key agreement, also known as information reconciliation and privacy amplification over unsecured channels, was shown to be theoretically feasible by Renner and Wolf (Eurocrypt 2004), although no protocol that runs in polynomial time was described. We propose a protocol that is not only polynomial-time, but actually practical, requiring only a few seconds on consumer-grade computers. Our protocol can be seen as an interactive version of robust fuzzy extractors (Boyen et al., Eurocrypt 2005, Dodis et al., Crypto 2006). While robust fuzzy extractors, due to their noninteractive nature, require w to have entropy at least half its length, we have no such constraint. In fact, unlike in prior solutions, in our solution the entropy loss is essentially unrelated to the length or the entropy of w, and depends only on the security parameter.

Note: Includes new subsection with a more detailed discussion on comparison with prior work. Corrected many minor typos and bugs.

Available format(s)
Publication info
Published elsewhere. Unknown where it was published
Robust Fuzzy ExtractorsPrivacy AmplificationInformation ReconciliationImplementation
Contact author(s)
bhavanak @ bu edu
2011-06-24: last of 7 revisions
2008-12-02: received
See all versions
Short URL
Creative Commons Attribution


      author = {Bhavana Kanukurthi and Leonid Reyzin},
      title = {Key Agreement from Close Secrets over Unsecured Channels},
      howpublished = {Cryptology ePrint Archive, Paper 2008/494},
      year = {2008},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.