Score:0

# How Can Indistinguishability be Proven?

I'm curious on how computational indistinguishably is proved.

For instance, would the following be computational indistinguishable? If it is, how do we prove it?

Let $$P_a$$ be a probabilistic machine which knows a secret $$a$$ and generates a sequence of $$n$$ tuples: $$(x_1,{x_1}^a),...,(x_n,{x_n}^a)$$ where the $$x_i$$ for each tuple is randomly sampled from a prime order cyclic group. Similarly, let a PPT $$P_b$$ be defined. Now let a challenger randomly pick two sequences generated by $$P_a$$ and $$P_b$$ (they could be both from $$P_a$$, or one from $$P_a$$ and one from $$P_b$$). Can one efficient algorithm tell if the two sequences are generated by two different PPTs?

We'll assume that the standard assumptions on groups apply, e.g., difficulty of discrete logarithm or decision Diffie-Hellman.

Are those exponentiations over the integers? If yes, just compute the logarithms and check whether they are the same.
Forgot to mention that \$x_i\$ belongs to a prime order cyclic group
We prove indistinguishablity by showing a reduction between the distibguisher and some problem believed to be hard.