Cryptography Reference
In-Depth Information
APPENDIX
B
Brief Outline of Volume 2
This first volume contains only material on the
basic tools
of modern cryptography,
that is, one-way functions, pseudorandomness, and zero-knowledge proofs. These ba-
sic tools are used in the construction of the
basic applications
(to be covered in the
second volume). The latter will cover encryption, signatures, and general cryptographic
protocols. In this appendix we provide brief summaries of the treatments of these basic
applications.
B.1. Encryption: Brief Summary
Both private-key and public-key encryption schemes consist of three efficient algo-
rithms:
key generation
,
encryption
, and
decryption
. The difference between the two
types of schemes is reflected in the definition of security: The security of a public-key
encryption scheme should also hold when the adversary is given the encryption key,
whereas that is not required for private-key encryption schemes. Thus, public-key en-
cryption schemes allow each user to broadcast its encryption key, so that any other user
can send it encrypted messages (without needing to first agree on a private encryption
key with the receiver). Next we present definitions of security for private-key encryption
schemes. The public-key analogies can be easily derived by considering adversaries
that get the encryption key as additional input. (For private-key encryption schemes,
we can assume, without loss of generality, that the encryption key is identical to the
decryption key.)
B.1.1. Definitions
For simplicity, we consider only the encryption of a single message; however, this mes-
sage can be longer than the key (which rules out information-theoretic secrecy [200]).
We present two equivalent definitions of security. The first, called
semantic security
,
is a computational analogue of Shannon's definition of
perfect secrecy
[200]. The se-
cond definition views secure encryption schemes as those for which it is infeasible to
distinguish encryptions of any (known) pair of messages (e.g., the all-zeros message
338
