Discrete Mathematics - Contemporary Cryptography - page 50

and represents an instance of the family F . Consequently, F is a collection or
ensemble of mappings. Every key k K or map f k occurs with some probability,

and hence there is a probability distribution on K .If K =

∈

n

{ 0 , 1 } and all keys are

uniformly distributed, then

u
←

k K

refers to an n -bit key k that is randomly chosen from K .Furthermore,

u
←

f F

refers to a function f k that is randomly chosen from F . This can be translated into
k

u
←

f k (in this sequence). In other words, f is the function f k ,where k is
a randomly chosen key.
We sometimes use the term Rand X→Y to refer to the family of all functions
from the domain X to the codomain Y .If X = Y , then we are talking about the
family of all permutations on X , and we use the term Perm X→X or P ( X ) to refer
to it. Permutations and families of permutations are further addressed in Section
3.1.4.

K ; f ←

The fact that ∗ is a binary operation on S means that it actually defines a

function from S × S into S .If a, b ∈ S , then the use of ∗ can be expressed as

follows:

∗ : S × S −→ S

( a, b ) −→ a ∗ b

This expression suggests that two arbitrary elements a, b ∈ S are mapped

to a new element a may have specific

properties. We are mainly interested in commutative and associative operations as
formally expressed in Definitions 3.1 and 3.2.

∗ b ∈ S . In this setting, the operation ∗

Definition 3.1 (Commutative operation) A binary operation ∗ is commutative if

a ∗ b = b ∗ a for all a, b ∈ S .

Definition 3.2 (Associative operation) A binary operation ∗ is associative if a ∗ ( b ∗

c )=( a ∗ b ) ∗ c for all a, b, c ∈ S .

may have (left and right) identity elements as
formally introduced in Definitions 3.3-3.5.

A commutative operation ∗