Discussion:
Question on indistinguishability
c***@yahoo.com
2006-08-15 10:24:51 UTC
Raw Message
Let the distributions {(u, x)} and {(u, * )} be computationally
indistinguishable. Here * represents a random string, while x is
related to u.

Let there exist an algorithm A that takes as input an element from the
first distribution and outputs a value v,

i.e. A(u, x) = v

Can I assume that there exists another algorithm B that takes in as
input simply u and outputs v with almost the same probability that
algorithm A outputs v on inputs (u, x).

i.e. B(u) = v

In other words, I want to assume that the second input to algorithm A
does not give any additional advantage in computing v. I am claiming
that this should hold because of the indistinguishability of the two
distribtions.

Is my claim true? If this is false, can anyone provide a counter
example? Any references to similar problems would also be nice.

Rgds
David Wagner
2006-08-17 06:04:44 UTC
Raw Message
Post by c***@yahoo.com
Let the distributions {(u, x)} and {(u, * )} be computationally
indistinguishable. Here * represents a random string, while x is
related to u.
Let there exist an algorithm A that takes as input an element from the
first distribution and outputs a value v,
i.e. A(u, x) = v
Can I assume that there exists another algorithm B that takes in as
input simply u and outputs v with almost the same probability that
algorithm A outputs v on inputs (u, x).
i.e. B(u) = v
Is this a homework problem? Sounds like something that would make a
good homework problem, so let me just give you some hints.

If you think that such an algorithm B is guaranteed to exist, the way to
be sure is to prove a theorem to that effect. How would you go about
proving it? How would you go about constructing such an algorithm B?
If I gave you a magical black box that implements algorithm A (i.e.,
you send values u and x to its input port, and it responds with value
v upon its output port), is there a systematic procedure you could use
to construct an algorithm B that is guaranteed to always work? If you
had a magical black box like that, and a value u, is there any way you
could come up with the value v that you're looking for? If you think
the answer is "yes", can you prove it?

Last, my standard advice: If this is a homework problem and you're