# Conditionally-Perfect Secrecy and a Provably-Secure Randomized Cipher

## Ueli Maurer

```
```Shannon's pessimistic theorem, which states that a cipher can be
perfect only when the entropy of the secret key is at least as great as
that of the plaintext, is relativized by the demonstration of a
randomized cipher in which the secret key is short but the plaintext
can be very long. This cipher is shown to be ``perfect with high
probability". More precisely, the eavesdropper is unable to obtain any
information about the plaintext when a certain security event occurs,
and the probability of this event is shown to be arbitrarily close to
one unless the eavesdropper performs an infeasible computation. This
cipher exploits the assumed existence of a publicly-accessible string
of random bits whose length is much greater than that of all the
plaintext to be encrypted; this is a feature that our cipher has in
common with the previously considered ``book ciphers''. Two
modifications of this cipher are discussed that may lead to practical
provably-secure ciphers based on either of two assumptions that appear
to be novel in cryptography, viz., the (sole) assumption that the
enemy's memory capacity (but not his computing power) is restricted and
the assumption that an explicit function is, in a specified sense,
controllably-difficult to compute, but not necessarily one-way.

Keywords: provable security, perfect secrecy, information theory,
randomized encryption, public randomness, book cipher.