Cryptography Reference
In-Depth Information
verdict that the sample was drawn according to the first distribution.
Saying that the two distributions are computationally indistinguishable
means that if
D
is a feasible procedure then its verdict is not really
meaningful (because the verdict is almost as often 1 when the input is
drawn from the first distribution as when the input is drawn from the
second distribution).
Indistinguishability by multiple samples
We comment that, for “eciently constructible” distributions, indis-
tinguishability by a single sample (as defined above) implies indistin-
guishability by multiple samples (see (65, Sec. 3.2.3)). The proof of
this fact provides a simple demonstration of a central proof technique,
known as a
hybrid argument
, which we briefly present next.
To prove that a sequence of independently drawn samples of one dis-
tribution is indistinguishable from a sequence of independently drawn
samples from the other distribution, we consider
hybrid
sequences such
that the
i
th
hybrid consists of
i
samples taken from the first distribution
and the rest taken from the second distribution. The “homogeneous”
sequences (which we wish to prove to be computational indistinguish-
able) are the extreme hybrids (i.e., the first and last hybrids consid-
ered above). The key observation is that distinguishing the extreme
hybrids (towards the contradiction hypothesis) yields a procedure for
distinguishing single samples of the two distributions (contradicting the
hypothesis that the two distributions are indistinguishable by a single
sample). Specifically, if
D
distinguishes the extreme hybrids, then it
also distinguishes a random pair of neighboring hybrids (i.e.,
D
distin-
guishes the
i
th
hybrid from the
i
+1
st
hybrid, for a randomly selected
i
). Using
D
, we obtain a distinguisher
D
of single samples: Given a
single sample,
D
selects
i
at random, generates
i
samples from the
first distribution and the rest from the second, and invokes
D
with
the corresponding sequence, while placing the input sample in location
i
+ 1 of the sequence. We stress that although the original distinguisher
D
(arising from the contradiction hypothesis) was only “supposed to
work” for the extreme hybrids, we can consider
D
's performance on
