International Association
for Cryptologic Research

We study a classical problem of privacy amplification, where two parties Alice and Bob share a weak secret X of min-entropy k, and wish to agree on secret key $R$ of length $m$ over a public communication channel completely controlled by a computationally unbounded attacker Eve.

Despite being extensively studied in the literature, the design of (efficient) \"optimal\" privacy amplification protocols is still open. Part of the reason is that there are quite a few important efficiency/security goals when designing privacy amplification protocols. The most basic such goal is to minimize the {\\em entropy loss} L=k-m, and it is known that the optimal value for L=O(\\lambda), where \\eps=2^{-\\lambda} is the desired security of the protocol. Other important considerations include (1) minimizing the number of communication rounds, (2) achieving strongest security notion called {\\em post-application robustness}, and (3) ensuring that the protocol $P$ does not leak some ``useful information\'\' about the source $X$ (this is called {\\em source privacy}). Additionally,

when trying to extract a key R which is much shorter than the source length |X| (and, often, the min-entropy bound k), \"Goal (0)\" of minimizing the entropy loss is replaced by asking (4) if P can be made {\\em locally computable} (meaning it reads only O(|R|) bits of X; this is called the {\\em Bounded Retrieval Model} (BRM)), and/or (5) if P can be sequentially run to extract the optimal number t = \\Theta(k/\\lambda) of session keys R_1,...,R_t of length m=O(\\lambda) each.

As a result, {\\em all} existing protocols in the literature fail to achieve at least two of Goals (0)-(3) (or, when |R|