Cryptographic Systems - Contemporary Cryptography - page 32

a PRBG, and a PRBG can be used to construct a PRF family (the corresponding
constructions are given in Section 13.2).
Because the notion and use of PRFs is a more advanced topic, we don't
provide an informal definition at this point. Instead, we refer to Chapter 13, where
we introduce, discuss, and put into perspective random functions, PRFs, and some
applications of PRFs in modern cryptography.

2.3 PUBLIC KEY CRYPTOSYSTEMS

According to Definition 1.7, public key cryptosystems use secret parameters that are
not shared between the participating entities. Instead, each entity holds a set of secret
parameters (collectively referred to as the private key ) and publishes another set of
parameters (collectively referred to as the public key ) that don't have to be secret
and can be published at will. 6 A necessary (but usually not sufficient) condition
for a public key cryptosystem to be secure is that it is computationally infeasible
to compute the private key from the public key. In this topic, k is frequently used
to refer to a public key, whereas k − 1 is used to refer to the corresponding private
key. Because public key cryptography is computationally less efficient than secret
key cryptography, public key cryptosystems are mainly used for authentication
and key management. The resulting cryptosystems combine secret and public key
cryptography and are often called hybrid . In fact, hybrid cryptosystems are very
frequently used in practice.
Note that the fact that public key cryptosystems use secret parameters that are
not shared between the participating entities implies that the corresponding algo-
rithms must be executed by different entities. Consequently, such cryptosystems are
typically defined as sets of algorithms (that may be executed by different entities).
We adopt this viewpoint in this topic. Examples of public key cryptosystems include
asymmetric encryption systems and DSSs, as well as cryptographic protocols for
key agreement, entity authentication, and secure multiparty computation. We have a
preliminary look at these examples.

2.3.1 Asymmetric Encryption Systems

Similar to a symmetric encryption system, an asymmetric encryption system can be
used to encrypt and decrypt (plaintext) messages. The major difference between a
symmetric and an asymmetric encryption system is that the former employs secret

6 It depends on the cryptosystem, whether it matters which set of parameters is used to represent the

private key and which set of parameters is used to represent the public key.