# Unconditional Authenticity and Privacy from an Arbitrarily Weak Secret

## Renato Renner and Stefan Wolf

```
```Unconditional cryptographic security cannot be generated simply from
scratch, but must be based on some given primitive to start with (such
as, most typically, a private key). Whether or not this implies that
such a high level of security is necessarily impractical depends on
how weak these basic primitives can be, and how realistic it is
therefore to realize or find them in|classical or quantum|reality. A
natural way of minimizing the required resources for
information-theoretic security is to reduce the length of the private
key. In this paper, we focus on the level of its secrecy instead and
show that even if the communication channel is completely insecure, a
shared string of which an arbitrarily large fraction is known to the
adversary can be used for achieving fundamental cryptographic goals
such as message authentication and encryption. More precisely, we
give protocols|using such a weakly secret key|allowing for both the
exchange of authenticated messages and the extraction of the key's
entire amount of privacy into a shorter virtually secret key. Our
schemes, which are highly interactive, show the power of two-way
communication in this context: Under the given conditions, the same
objectives cannot be achieved by one-way communication only.