Introduction - Mathematics of Public Key Cryptography - page 5

authentic copy of the public key is not covered by this definition; the public key is an input
to the encryption function.

Definition 1.3.1 Let κ be a security parameter (note that κ is not necessarily the

same as the “key length”; see Example 1.3.2 ). An encryption scheme is defined by the
following spaces (all depending on the security parameter κ ) and algorithms:

∈ N

M κ

the space of all possible messages;

PK κ

the space of all possible public keys;

SK κ

the space of all possible private keys;

C κ

the space of all possible ciphertexts;

KeyGen a randomised algorithm that takes the security parameter κ , runs in

expected polynomial-time (i.e., O ( κ c ) bit operations for some constant
c

∈ N ) and outputs a public key pk ∈ PK κ and a private key sk ∈ SK κ ;

Encrypt a randomised algorithm that takes as input m M κ and pk , runs in

expected polynomial-time (i.e., O ( κ c ) bit operations for some constant
c

∈

∈ N ) and outputs a ciphertext c ∈ C κ ;

Decrypt an algorithm (not usually randomised) that takes c ∈ C κ and sk ,

runs in polynomial-time and outputs either m ∈ M κ or the

invalid ciphertext symbol ⊥ .

It is required that

Decrypt(Encrypt( m , pk ) , sk ) =

m

if ( pk , sk ) is a matching key pair. Typically, we require that the fastest known attack on the
system requires at least 2 κ bit operations.

Example 1.3.2 We sketch how to write “textbook” RSA encryption in the format of
Definition 1.3.1 . The KeyGen algorithm takes input κ and outputs a modulus N that is
a product of two randomly chosen primes of a certain length, as well as an encryption
exponent e . Giving a precise recipe for the bit-length of the primes as a function of the
security parameter is non-trivial for RSA; we merely note here that if κ

128 (i.e., so that
there is no known attack on the system performing fewer than 2 128 bit operations) then it is
standard to use 1536-bit primes. As we will discuss in Chapter 12 , one can generate primes
in expected polynomial-time and hence KeyGen is a randomised algorithm with expected
polynomial-time complexity.
The message space M κ depends on the randomised padding scheme being used. The
ciphertext space C κ in this case is (

=

) ∗ , which does not agree with Definition 1.3.1 as
it does not depend only on κ . Instead, one usually takes C κ to be the set of

Z /N Z

log 2 ( N ) -bit

strings.
The Encrypt and Decrypt algorithms are straightforward (though the details depend on
the padding scheme). The correctness condition is easily checked.