Score:0

How Can Indistinguishability be Proven?

yt flag

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.

cn flag
Are those exponentiations over the integers? If yes, just compute the logarithms and check whether they are the same.
Sean avatar
yt flag
Forgot to mention that $x_i$ belongs to a prime order cyclic group
Meir Maor avatar
in flag
We prove indistinguishablity by showing a reduction between the distibguisher and some problem believed to be hard.
cn flag
You likely have more information about that group. In $(\mathbb{Z}_p,+)$ the two are trivially distinguishable.
Sean avatar
yt flag
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 avatar
in flag
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.

Post an answer

Most people don’t grasp that asking a lot of questions unlocks learning and improves interpersonal bonding. In Alison’s studies, for example, though people could accurately recall how many questions had been asked in their conversations, they didn’t intuit the link between questions and liking. Across four studies, in which participants were engaged in conversations themselves or read transcripts of others’ conversations, people tended not to realize that question asking would influence—or had influenced—the level of amity between the conversationalists.