Cryptography Reference
In-Depth Information
situations. Hence, we believe that the notion of computational indistinguishability is a
very natural one.
3.2.1. Definition
The notion of computational indistinguishability is formulated in a way that is standard
in the field of computational complexity: by considering objects as infinite sequences
of strings. Hence, the sequences
y n } n N are said to be computationally
indistinguishable if no efficient procedure can tell them apart. In other words, no efficient
algorithm D can accept infinitely many x n 's while rejecting their y counterparts (i.e.,
for every efficient algorithm D and all sufficiently large n 's, it holds that D accepts x n
iff D accepts y n ). Objects that are computationally indistinguishable in this sense can
be considered equivalent as far as any practical purpose is concerned (because practical
purposes are captured by efficient algorithms, and they cannot distinguish these objects).
The foregoing discussion extends naturally to the probabilistic setting. Furthermore,
as we shall see, this extension yields very useful consequences. Loosely speaking, two
distributions are called computationally indistinguishable if no efficient algorithm can
tell them apart. Given an efficient algorithm D , we consider the probability that D
accepts (e.g., outputs 1 on input) a string taken from the first distribution. Likewise, we
consider the probability that D accepts a string taken from the second distribution. If
these two probabilities are close, we say that D does not distinguish the two distribu-
tions. Again, the formulation of this discussion is with respect to two infinite sequences
of distributions (rather than with respect to two fixed distributions). Such sequences are
called probability ensembles.
{
x n } n N and
{
Definition 3.2.1 (Probability Ensemble): Let I be a countable index set. An
ensemble indexed by I is a sequence of random variables indexed by I . Namely,
any X
={
X i } i I , where each X i is a random variable, is an ensemble indexed
by I .
We shall use either
N
or a subset of
{
0
,
1
} as the index set. Typically in our applica-
tions, an ensemble of the form X
X n } n ∈N has each X n ranging over strings of length
poly( n ), whereas an ensemble of the form X
={
={
X w } w ∈{ 0 , 1 } will have each X w ranging
over strings of length poly(
| w |
). In the rest of this chapter we shall deal with ensembles
indexed by
, whereas in other chapters (e.g., in the definition of secure encryption and
zero-knowledge) we shall deal with ensembles indexed by strings. To avoid confusion,
we shall present variants of the definition of computational indistinguishability for each
of these two cases. The two formulations can be unified if one associates the natural
numbers with their unary representations (i.e., associate N and { 1 n : n ∈N} ).
N
Definition 3.2.2 (Polynomial-Time Indistinguishability):
def
={
1. Variant
for
ensembles
indexed
by
N
:
Two
ensembles,
X
X n } n ∈N
and
def
={
Y
are indistinguishable in polynomial time if for every probabi-
listic polynomial-time algorithm D, every positive polynomial
Y n } n ∈N ,
p (
·
) , and all
Search WWH ::




Custom Search