c***@yahoo.com

2006-08-15 10:24:51 UTC

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.

Thanks in advance.

Rgds

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.

Thanks in advance.

Rgds