Cryptography Reference
In-Depth Information
In addition to these constructions of cryptographically secure PRBGs, Andrew
C. Yao showed that they are all perfect in the sense that no PPT algorithm can guess
with a probability significantly greater than 1
/
2 whether an input string of length
k
was randomly selected from
k
or generated by such a PRBG [12]. Note that
this notion of a perfect PRBG is conceptually similar to the Turing Test
3
used in
artificial intelligence [13]. One can rephrase Yao's result by saying that a PRBG
that passes the Blum-Micali next-bit test is perfect in the sense that it passes all
polynomial-time statistical tests.
The Blum-Micali and BBS PRBGs, together with the proof of Yao, represent
a major achievement in the development of cryptographically secure PRBGs. More
recently, it was shown that the existence of a one-way function is equivalent to
the existence of a cryptographically secure PRBG (i.e., a PRBG that passes all
polynomial-time statistical tests) [14].
On a high level of abstraction, one can say that a PRBG is called cryptograph-
ically secure if the (pseudorandom) bit sequence it generates and outputs cannot be
distinguished (by any PPT algorithm) from a true random bit sequence of the same
length. In analogy, one may not care if a pseudorandom bit sequence is random
or not; all one may care about is whether a difference can be observed between
the pseudorandomly generated bit sequence and a true random bit sequence (of the
same length). Consequently, the notion of
effective similarity
(as, for example, used
in [12, 15]) or
computational indistinguishability
are fundamental for the definition
of cryptographically secure PRBGs. To make these ideas more precise, let
{
0
,
1
}
X
=
{
X
n
}
=
{
X
n
}
n∈
N
=
{
X
1
,X
2
,X
3
,...
}
and
Y
=
{
Y
n
}
=
{
Y
n
}
n∈
N
=
{
Y
1
,Y
2
,Y
3
,...
}
3
The Turing Test is meant to determine if a computer program has intelligence. According to Alan
M. Turing, the test can be devised in terms of a game (a so-called imitation game). It is played
with three people, a man (A), a woman (B), and an interrogator (C) who may be of either sex. The
interrogator stays in a room apart from the other two. The object of the game for the interrogator is
to determine which of the other two is the man and which is the woman. He knows them by labels
X and Y, and at the end of the game he says either “X is A and Y is B” or “X is B and Y is A.”
The interrogator is allowed to put questions to A and B. When talking about the Turing Test today,
what is generally understood is the following: the interrogator is connected to one person and one
machine via a terminal, and therefore can't see her counterparts. Her task is to find out which of
the two candidates is the machine and which is the human only by asking them questions. If the
machine can “fool” the interrogator, it is intelligent.
