Cryptography Reference
In-Depth Information
•
A
tag space
T
;
•
A
key space
K
;
•
A family
A
=
{
A
k
:
k
∈K}
of
authentication functions
A
k
:
M→T
;
•
A family
V
=
{
V
k
:
K
∈K}
of
verification functions
V
k
:
M×T →
.
V
k
(
m, t
)
must yield
valid
if
t
is a valid authentication tag
for message
m
and key
k
(i.e.,
t
=
A
k
(
m
)
).
For every key
k
{
valid, invalid
}
∈K
and every message
m
∈M
,
V
K
(
m, A
K
(
m
))
must yield
valid
.
}
∗
,
l
tag
for some fixed tag length
l
tag
,and
Typically,
M
=
{
0
,
1
T
=
{
0
,
1
}
l
key
for some fixed key length
l
key
(e.g.,
l
tag
=
l
key
= 128).
Many message authentication systems have been developed and proposed
in the literature. Some of these systems are unconditionally (i.e., information-
theoretically) secure, but most of them are conditionally (i.e., computationally)
secure. The most important message authentication systems are overviewed, dis-
cussed, and put into perspective in Chapter 11.
K
=
{
0
,
1
}
2.2.3
PRBGs
In Section 2.1.3 we mentioned that random bit generators are important building
blocks for many cryptographic systems, and that there is no deterministic (compu-
tational) realization or implementation of such a generator, but that there are non-
deterministic realizations and implementations making use of physical events and
phenomena. Unfortunately, these realizations and implementations are not always
appropriate, and there are situations in which one needs to deterministically generate
binary sequences that appear to be random (e.g., if one needs a random bit generator
but none is available, or if one must make statistical simulations or experiments
that can be repeated as needed). Also, one may have a short random bit sequence
that must be stretched into a long sequence. This is where the notion of a PRBG as
illustrated in Figure 2.6 and introduced in Definition 2.9 comes into play.
5
Again, the
definition is not precise in a mathematically strong sense, because we have neither
defined the notion of an efficient algorithm nor have we specified what we really
mean by saying that a binary sequence “appears to be random.”
Definition 2.9 (Pseudorandom bit generator)
A
PRBG
is an efficient determinis-
tic algorithm that takes as input a random binary sequence of length
k
(i.e., the
seed
) and generates as output another binary sequence (i.e., the
pseudorandom bit
sequence
) of length
l
k
that appears to be random.
5
Note the subtle difference between Figures 2.3 and 2.5. Both generators output a binary sequence.
The random bit generator has no input, whereas the PRBG has a seed that serves as input.