Skip to main content
Bumped by Community user
Bumped by Community user
Bumped by Community user
Bumped by Community user
Bumped by Community user
latex syntax
Source Link
kelalaka
  • 49.5k
  • 12
  • 118
  • 205

All the examples that I see for proving that two distributions are not computationally indistinguishable involve a pattern: choose a Distinguisher D(.)$D(\cdot)$ such that D(x)$D(x)$ is 1$1$ if x$x$ satisfies some certain properties.

For example, consider the distribution $X$ such that it contains all the binary strings in $\{0,1\}^k$ such that they end with 1 and distribution $Y$ uniformly spread over all strings in $\{0,1\}^k$. Now I can choose my distinguisher to be $D(x) = 1$, if $x$ ends with 1$1$.

However, if there is no such pattern in our distributions, how can we prove that the given distributions are (not) computationally indistinguishable?

All the examples that I see for proving that two distributions are not computationally indistinguishable involve a pattern: choose a Distinguisher D(.) such that D(x) is 1 if x satisfies some certain properties.

For example, consider the distribution $X$ such that it contains all the binary strings in $\{0,1\}^k$ such that they end with 1 and distribution $Y$ uniformly spread over all strings in $\{0,1\}^k$. Now I can choose my distinguisher to be $D(x) = 1$, if $x$ ends with 1.

However, if there is no such pattern in our distributions, how can we prove that the given distributions are (not) computationally indistinguishable?

All the examples that I see for proving that two distributions are not computationally indistinguishable involve a pattern: choose a Distinguisher $D(\cdot)$ such that $D(x)$ is $1$ if $x$ satisfies some certain properties.

For example, consider the distribution $X$ such that it contains all the binary strings in $\{0,1\}^k$ such that they end with 1 and distribution $Y$ uniformly spread over all strings in $\{0,1\}^k$. Now I can choose my distinguisher to be $D(x) = 1$, if $x$ ends with $1$.

However, if there is no such pattern in our distributions, how can we prove that the given distributions are (not) computationally indistinguishable?

Source Link

Example of not computationally indistinguishable

All the examples that I see for proving that two distributions are not computationally indistinguishable involve a pattern: choose a Distinguisher D(.) such that D(x) is 1 if x satisfies some certain properties.

For example, consider the distribution $X$ such that it contains all the binary strings in $\{0,1\}^k$ such that they end with 1 and distribution $Y$ uniformly spread over all strings in $\{0,1\}^k$. Now I can choose my distinguisher to be $D(x) = 1$, if $x$ ends with 1.

However, if there is no such pattern in our distributions, how can we prove that the given distributions are (not) computationally indistinguishable?