# One-Way Secret-Key Agreement and Applications to Circuit Polarization and Immunization of Public-Key Encryption

## Thomas Holenstein and Renato Renner

```
```Secret-key agreement between two parties Alice and Bob, connected by
an insecure channel, can be realized in an information-theoretic
sense if the parties share many independent pairs of correlated and
partially secure bits. We study the special case where only one-way
communication from Alice to Bob is allowed and where, for each of
the bit pairs, with a certain probability, the adversary has no
information on Alice's bit. We give an expression which, for this
situation, exactly characterizes the rate at which Alice and Bob can
generate secret key bits.
This result can be used to analyze a slightly restricted variant of
the problem of polarizing circuits, introduced by Sahai and Vadhan
in the context of statistical zero-knowledge, which we show to be
equivalent to secret-key agreement as described above. This
provides us both with new constructions to polarize circuits, but
also proves that the known constructions work for parameters which
are tight.
As a further application of our results on secret-key
agreement, we show how to immunize single-bit public-key encryption
schemes from decryption errors and insecurities of the encryption, a
question posed and partially answered by Dwork, Naor, and Reingold.
Our construction works for stronger parameters than the known
constructions.