Theory of Cryptography pdf

Theory of Cryptography Wonderful Digest

Either the key length n must be exponential in the message length b, or One can deterministically extract almost b nearly random bits from the key.

In particular, in the case when b is large enough, so that it is infeasible to sample more than 2 b (imperfect) bits for one’s secret key, our result implies the following. In order to build a secure b-bit encryption scheme, one must come up with a source of randomness from which one can already deterministically extract almost b nearly random bits! Notice, since such extracted bits can then be used as a one-time pad, we get that any b-bit encryption scheme can in principle be
converted to a “one-time-pad-like” scheme capable of encrypting nearly b bits! In this sense, our results show that, for the purpose of information-theoretically encrypting a “non-trivial” number of bits, the one-time pad scheme is essentially“universal”.