2006-08-15 10:24:51 UTC
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
Is my claim true? If this is false, can anyone provide a counter
example? Any references to similar problems would also be nice.
Thanks in advance.