*15:17*[Pub][ePrint] Privacy Amplification with Asymptotically Optimal Entropy Loss, by Nishanth Chandran and Bhavana Kanukurthi and Rafail Ostrovsky and Leonid Reyzin

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).