## Cryptology ePrint Archive: Report 2012/501

**Privacy Amplification with Asymptotically Optimal Entropy Loss**

*Nishanth Chandran and Bhavana Kanukurthi and Rafail Ostrovsky and Leonid Reyzin*

**Abstract: **We study the problem of ``privacy amplification'': key agreement
between two parties who both know a weak secret w, such as a
password. (Such a setting is ubiquitous on the internet, where
passwords are the most commonly used security device.) We assume
that the key agreement protocol is taking place in the presence of
an active computationally unbounded adversary Eve. The adversary may
have partial knowledge about w, so we assume only that w has
some entropy from Eve's point of view. Thus, the goal of the
protocol is to convert this non-uniform secret w into a uniformly
distributed string $R$ that is fully secret from Eve. R may then
be used as a key for running symmetric cryptographic protocols (such
as encryption, authentication, etc.).

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 format(s): **Postscript (PS) | Compressed Postscript (PS.GZ) | PDF | BibTeX Citation

**Version: **20120903:130238 (All versions of this report)

**Discussion forum: **Show discussion | Start new discussion

[ Cryptology ePrint archive ]