Cryptography Reference
In-Depth Information
model. Using the notion of Turing machine, we can limit the time or memory com-
plexity. It can also be
deterministic
or
probabilistic
, but this is no real limitation as the
complexity is not bounded.
5
Usually, we only limit the number of
oracle calls
.
In this section we consider two important security models. We consider distin-
guishers which have to prepare all their queries to the oracle at the same time and with
a limited number of oracle calls
d
. These are called
nonadaptive
distinguishers. In
practice, they correspond to attacks which can play with an encryption device within a
limited time period so that they have no time to prepare their questions in an adaptive
way. We also consider distinguishers which are limited to
d
oracle calls, but which can
make their queries depend on the oracle feedback from the previous ones. These are
called
adaptive
distinguishers. We let Cl
na
and Cl
a
be the class of all nonadaptive and
adaptive distinguishers, respectively.
We measure the resistance against a class of distinguishers Cl by the best advantage.
Formally, if
C
and
C
∗
are two random oracles, we define
T
∈
Cl
E
(
T
C
)
E
(
T
C
∗
)
C
∗
)
,
=
−
BestAdv
Cl
(
C
max
where
T
C
denotes the output of the distinguisher
T
when interacting with the random
oracle
C
. Most of distinguisher classes are symmetric in the sense that if a distinguisher
T
is in the class, then the opposite distinguisher 1
T
is also in the class. Therefore,
there is no need for looking at the absolute value of the advantage.
−
We can motivate the notion of indistinguishability from an ideal function as one
of the strongest security requirements for all conventional cryptographic primitives.
In the case of a block cipher
C
, for instance, when an adversary is able to decrypt a
ciphertext after having queried
d
1 chosen plaintexts, he can
a fortiori
use this attack
in order to distinguish
C
from a truly random permutation
C
∗
within
d
queries: if the
ciphertext decrypts correctly, then the oracle implements
C
. Hence, if the block cipher
C
is indistinguishable from
C
∗
within
d
queries, then the encryption is safe when used
at most
d
times.
−
1 queries
to a MAC algorithm
F
, he can distinguish
F
from a truly random function
F
∗
within
d
queries. So if
F
is indistinguishable from
F
∗
, then the MAC function
F
is secure
when used at most
d
times.
Similarly, if an adversary can forge an authenticated message after
d
−
On the hash function side, we can prove that when we are given a truly random
oracle function
F
∗
, then we cannot find collisions in
F
∗
essentially better than by doing a
birthday paradox attack, and we cannot perform first or second preimage attacks against
F
∗
essentially better than by doing exhaustive search. Therefore, under the assumption
that a hash function can be simulated by a random oracle which is indistinguishable
from
F
∗
, a hash function is also a secure hash function.
5
See Chapter 8.
Search WWH ::
Custom Search