Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style

Reports tagged with Computational Indistinguishability:
TR95-056 | 26th November 1995
Oded Goldreich

Three XOR-Lemmas -- An Exposition

We provide an exposition of three Lemmas which relate
general properties of distributions
with the exclusive-or of certain bit locations.

The first XOR-Lemma, commonly attributed to U.V. Vazirani,
relates the statistical distance of a distribution from uniform
to the maximum bias of the xor of certain bit positions.
more >>>

TR96-067 | 20th December 1996
Oded Goldreich, Bernd Meyer

Computational Indistinguishability -- Algorithms vs. Circuits.

We present a simple proof to the existence of a probability ensemble
with tiny support which cannot be distinguished from the uniform ensemble
by any recursive computation.
Since the support is tiny (i.e, sub-polynomial),
this ensemble can be distinguish from the uniform ensemble
by a (non-uniform) family ... more >>>

TR98-017 | 29th March 1998
Oded Goldreich, Madhu Sudan

Computational Indistinguishability: A Sample Hierarchy.

We consider the existence of pairs of probability ensembles which
may be efficiently distinguished given $k$ samples
but cannot be efficiently distinguished given $k'<k$ samples.
It is well known that in any such pair of ensembles it cannot be that
both are efficiently computable
(and that such phenomena ... more >>>

TR09-031 | 6th April 2009
Zvika Brakerski, Oded Goldreich

From absolute distinguishability to positive distinguishability

We study methods of converting algorithms that distinguish pairs
of distributions with a gap that has an absolute value that is noticeable
into corresponding algorithms in which the gap is always positive.
Our focus is on designing algorithms that, in addition to the tested string,
obtain a ... more >>>

TR21-140 | 27th September 2021
Nathan Geier

Tight Computational Indistinguishability Bound of Product Distributions

Assume that $X_0,X_1$ (respectively $Y_0,Y_1$) are $d_X$ (respectively $d_Y$) indistinguishable for circuits of a given size. It is well known that the product distributions $X_0Y_0,\,X_1Y_1$ are $d_X+d_Y$ indistinguishable for slightly smaller circuits. However, in probability theory where unbounded adversaries are considered through statistical distance, it is folklore knowledge that in ... more >>>

ISSN 1433-8092 | Imprint