Chapter 4. Computational Complexity

4.1 Introduction

If a random variable follows the uniform distribution and is independent from any given information, then there is no way to relate a uniformly random variable to any other information by any means of “computation.” This is exactly the security basis behind the only unconditionally (or information-theoretically) secure encryption scheme: one-time pad, that is, mixing a uniformly random string (called key string) with a message string in a bit by bit fashion (see §7.3.3). The need for independence between the key string and the message string requires the two strings to have the same length. Unfortunately, this poses an almost unpassable limitation for a practical use of the one-time-pad ...

Get Modern Cryptography: Theory and Practice now with O’Reilly online learning.

O’Reilly members experience live online training, plus books, videos, and digital content from 200+ publishers.