ABSTRACT

This chapter begins the study of modern cryptography by introducing the weaker notion of computational secrecy. It shows how this definition can be used to bypass the impossibility results shown previously for perfect secrecy and, in particular, how a short key can be used to encrypt many long messages. The concrete approach to computational security quantifies the security of a cryptographic scheme by explicitly bounding the maximum success probability of a adversary running for some specified amount of time or, more precisely, investing some specified amount of computational effort. Any security definition consists of two components: a definition of what is considered a “break” of the scheme, and a specification of the power of the adversary. Computational secrecy introduces two relaxations of perfect secrecy: first, secrecy is guaranteed only against efficient adversaries; second, secrecy may “fail” with small probability.