How Can Indistinguishability be Proven?

Sean

11/24/22, 12:11 PM

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.

0 + 6

indistinguishability

Maeher

11/24/22, 1:11 PM

Are those exponentiations over the integers? If yes, just compute the logarithms and check whether they are the same.

Sean

11/24/22, 4:22 PM

Forgot to mention that $x_i$ belongs to a prime order cyclic group

Meir Maor

11/24/22, 5:00 PM

We prove indistinguishablity by showing a reduction between the distibguisher and some problem believed to be hard.

Maeher

11/24/22, 5:19 PM

You likely have more information about that group. In $(\mathbb{Z}_p,+)$ the two are trivially distinguishable.

Sean

11/25/22, 12:57 AM

Thanks for the inputs. Let's say this is a prime order group where the discrete logarithm is assumed to be hard? My guess is that this can be somehow related to decision Diffie-Hellman but not very sure.

Maarten Bodewes

11/25/22, 4:52 PM

The question seems generic as it mentions DL-problem just as an example, but I'm not sure if you can prove any kind of indistinguishability without choosing a specific scheme.